
class Tree < MySingleton

  def self.initialize_singleton
    # pre index stuff, so the levels and order
    # are properly setup    
    tree = new
    tree.index_nodes
    tree
  end

  def clear_cache
    @__nodes = nil
    @__children = nil
    # the one who made the change should pay with his time
    puts "INDEX NODES"
    index_nodes
    self
  end

  def nodes
    if !@__nodes
      index_nodes
    end
    @__nodes
  end

  def nodes_by_identity identity
    nodes[identity]
  end

  def index_nodes
    index = {}
    breadth_first { |node|
      index[node.identity] = node

      node.tree = self

      if parent = index[node.parent_identity]
        node.parent_node = parent
      elsif node.is_root
        node.level = 0
      else
        raise "#{node.title} is not a root,"+
   "nor has parent. (identity #{node.identity})"
      end
    }
    @__nodes = index
    self
  end

  def children_of node
    @__children[node.identity]
  end

  def children
    @__children ||= childrenize(NodeThing.all.to_a)
  end

  def breadth_first roots = children[nil], &block
    each :breadth_first, roots, &block
  end

  def depth_first roots = children[nil], &block
    each :depth_first, roots, &block
  end

  def each kind, roots, &block
    #if no nodes to process, do nothing
    return unless roots

    # do not modify params
    process = roots.dup

    # limit the number of iterations
    # helps if crazy stuff happens
    i = 1000
    while process.length > 0 && (i -= 1) > 0
      node = process.shift
      block.call(node)
      next if node.nil? #hot fix
      if ch = children[node.identity]
        ch = ch.sort { |a, b|
          a.title.upcase <=> b.title.upcase
        }
        ch = ch.sort { |a, b|
          a.order <=> b.order
        }
        ch.first.first = true
        ch.last.last = true
      end
      if kind == :depth_first
        process = (ch || [])+process
      else #breadth first
        process += (ch || [])
      end
    end
    self
  end

  def childrenize nodes
    children = {}
    nodes.each { |node|
      (children[node.parent_identity] ||= []) << node
    }
    children
  end

  def destination(e)
    e.data['destination'] =
      find_destination(
        e.env[:unprocessed_tail].join("/"),
        e.env[:unprocessed_tail]
      )
  end

  def find_node_by_string_id string_id
    nodes.values.select {|n|
      n.string_id == string_id
    }.first
  end

  def find_destination tail, unprocessed_tail = []
    dest = nil
    tail = tail.split('/').reverse
    len = tail.length
    #tail = e.env[:unprocessed_tail]
    tail.each_with_index { |string_id, i|
      node = find_node_by_string_id(string_id)
      if node && node.level == (len - i)
        (i+1).times {
          unprocessed_tail.shift
        }
        dest = node
        break
      end
    }
    dest || root
  end

  def root
    nodes.values.select {|n| n.is_root }.first
  end




  

  class Test < AppTest
    def setup
      DataMapper.setup(:test, :adapter => 'in_memory')
    end

    def node options
      n = NodeThing.new(options)
      n.save
      n
    end

    def root
      node :string_id => 'root', :is_root => true
    end

    def destination url
      Tree.new.find_destination(url)
    end

    def test_empty_path_gives_root_destination
      repository(:test) {
        root = root()
        eq destination(''), root
      }
    end

    def test_path_with_single_node_gives_destination_node
      repository(:test) {
        node(:string_id => 'subpage', :parent_node => root())
        eq destination('subpage').string_id, 'subpage'
      }
    end

    def test_destination_for_sub_sub_page
      repository(:test) {
        node(
          :string_id => 'subsubpage',
          :parent_node => node(
            :string_id => 'subpage',
            :parent_node => root()
          )
        )
        eq destination('subpage/subsubpage').string_id,
          'subsubpage'
      }
    end
  end
end
